package com.tgy.dynamic.programming;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 2020-11-10 10:43
 */
public class ChangMoney {


    /**
     * 兑换零钱
     * @param money 待兑换的钱
     * @param smallMoneys 待兑换的零钱
     * @return 需要的零钱数
     */
    public int changeMoney(int money,int[] smallMoneys) {

        if (smallMoneys.length <= 0 || money <= 0) {

            return 0;
        }

        int[] smallMoneyNums = new int[money + 1];
        int[] beforeMoneys = new int[money + 1];

        for (int smallMoney : smallMoneys) {

            smallMoneyNums[smallMoney] = 1;
            beforeMoneys[smallMoney] = smallMoney;
        }

        int num, before;
        for (int i = 1; i <= money; i++) {

            if (smallMoneyNums[i] != 0) {
                continue;
            }
            num = Integer.MAX_VALUE;
            before = 0;
            for (int smallMoney : smallMoneys) {
                int sm;
                if (i > smallMoney && (sm = smallMoneyNums[i - smallMoney]) > 0) {

                   if (num > sm) {

                       num = sm;
                       before = smallMoney;
                   }
                }
            }

            if (num == Integer.MAX_VALUE || num == -1) {

                smallMoneyNums[i] = -1;
            }else {

                beforeMoneys[i] = before;
                smallMoneyNums[i] = num + 1;
            }

        }

        for (int i = 1; i <= money; i++) {

            printChangeMoney(i,beforeMoneys);
        }

        return smallMoneyNums[money];
    }

    private void  printChangeMoney(int money,int[] beforeMoney) {

        ArrayList<Integer> container = new ArrayList<>();
        int tmpM = money;
        while (true) {

            if (money <= 0) {

                break;
            }

            int mn = beforeMoney[money];

            if (mn == 0) {

                break;
            }
            container.add(mn);
            money -= mn;
        }

        if (container.size() > 0) {

            System.out.println(tmpM + " 组成:" + Arrays.toString(container.toArray(new Integer[0])));
        }else {

            System.out.println(tmpM + "无法兑换");
        }

    }
}
